package mcts;

import java.util.Collections;
import java.util.LinkedList;
import java.util.NoSuchElementException;
import java.util.Set;

import playout_policy.PlayoutPolicy;

import exceptions.AlreadyOccupiedException;
import exceptions.GameOverException;
import exceptions.IllegalMoveException;
import exceptions.ImpossibleMoveException;
import exceptions.KoViolationException;
import exceptions.SuicideMoveException;

import game.GoBoard;
import game.GoGame;

public class GoGameTree {
	
	GoGame game;
	GoGameTreeSonsList sons;
	boolean developed;
	int visited;
	int wins;
	int last_move_position;
	static PlayoutPolicy playout_policy;
	final static private int EXPAND_THRESHOLD = 5;
	final static private float c = (float) 1.4; //sqrt(2) in theory
	
	public GoGameTree(GoGame game) {
		this.game = game;
		this.sons = null;
		this.developed = false;
		this.visited = 0;
		this.wins = 0;
		try {
			this.last_move_position = game.getPlayedMoves().getLast();
		} catch (NoSuchElementException e) {
			// No move have been played so far
			last_move_position = -1;
		}
	}
	
	public GoGame getGame() {
		return this.game;
	}
	
	public GoGameTreeSonsList getSons() {
		return this.sons;
	}
	
	public float getEvaluation(int global_time) {
		
		float ucb;
		if (this.getColorToPlay() == GoBoard.BLACK) ucb = -(float) (c*Math.sqrt(Math.log(global_time)/(visited+1)));
		else ucb = (float) (c*Math.sqrt(Math.log(global_time)/(visited+1)));;
		
		if (visited == 0) return (float) 0.5+ucb;
				
		return (float) (((float)wins)/visited)+ucb;
	}
	
	public int getColorToPlay() {
		return game.getColorToPlay();
	}
	
	public int getVisited() {
		return visited;
	}
	
	public int getWins() {
		return wins;
	}
	
	public boolean isLeaf() {
		return (sons == null);
	}
	
	public void expand() {
		
		Set<Integer> free_moves = game.getBoard().getFreeIntersections();
		LinkedList<Integer> free_moves_list = new LinkedList<Integer>();
		free_moves_list.addAll(free_moves);
		Collections.shuffle(free_moves_list);
		
		for (int move : free_moves_list) {
			GoGame copy = new GoGame(game);
			try {
				copy.move(move);
				if (developed) {
					sons.insert(new GoGameTree(copy), visited);
				} else {
					sons = new GoGameTreeSonsList(new GoGameTree(copy));
					developed = true;
				}
			} catch (IllegalMoveException e) {
				//The move is illegal ; we don't add it in the tree
			} catch (ImpossibleMoveException e) {
				System.err.println("Internal error in tree expansion");
				e.printStackTrace();
			} catch (GameOverException e) {
				if (copy.isBlackWinning()) {
					//TODO
				}
			}
			
		}
	}
	
	static public void setPlayoutPolicy(PlayoutPolicy policy) {
		playout_policy = policy;
	}
	
	public void triggerOneSimulation(int global_time) throws GameOverException {
		if (isLeaf()) {
			
			if (this.visited > EXPAND_THRESHOLD) {
				this.expand();
			} else {
				GoGame c1 = new GoGame(game);
				GoGame c2;
				while(true) {
					try {
						c2 = playout_policy.generateMove(c1);
						c1 = c2;
					} catch (GameOverException e) {
						boolean black_win = e.getResult();
						if (black_win) this.wins += 1;
						this.visited += 1;
						throw e;
					}
					
				}
			}
			
		} else {
			GoGameTree best_son = this.getBestSon();
			try {
				best_son.triggerOneSimulation(global_time);
			} catch (GameOverException e) {
				boolean black_win = e.getResult();
				if (black_win) this.wins += 1;
				this.visited += 1;
				GoGameTreeSonsList copy = sons.updatePosition(best_son,global_time);
				sons = copy;
				throw e;
			}
		}
	}
	
	public GoGameTree getBestSon() {
		if (sons == null) return null;
		
		if (this.getColorToPlay() == GoBoard.BLACK) {
			return sons.getFirst();
		}
		
		return sons.getLast();
	}
	
	public GoGameTree getMostRobustSon() {
		if (sons == null) return null;
		
		int most_visit = -1;
		GoGameTree res = null;
		for (GoGameTree s : sons) {
			if (s.getVisited() > most_visit) {
				most_visit = s.getVisited();
				res = s;
			}
		}
		
		return res;
	}
	
	public int getLastMove() {
		return last_move_position;
	}
	
	public String getLastMoveLabel() {
		return game.getBoard().labelPosition(last_move_position);
	}
	
	public String printInfo(String prefix, int global_time) {
		String res = game.printInfo(prefix);
		res += "Simulations : "+visited+"\n";
		res += this.printSonsList(prefix, global_time);
		return res;
 	}
	
//	public void printTree(String prefix, int depth) {
//		if (depth == 0) return;
//		System.out.println(prefix+game.getBoard().labelPosition(last_move_position));
//		if (sons != null) {
//			for (GoGameTree s : sons) s.printTree(prefix+" | ", depth-1);
//		}
//	}
	
	public String printSonsList(String prefix,int global_time) {
		String res = prefix;
		if (sons != null) {
			for (GoGameTree node : sons) {
				res += node.getLastMoveLabel()+"("+node.getEvaluation(global_time)+"),";
			}
		}
		return res+"\n";
	}
	
	public int getDepth() {
		if (developed) {
			int r = 0;
			for (GoGameTree t : sons) r = Math.max(r, t.getDepth());
			return r+1;
		} else {
			return 0;
		}
	}
	
	public String getOptimalSequence(int n) {
		String best_first_move = this.getLastMoveLabel();
		if (sons == null || n == 0) return best_first_move;
		
		return best_first_move+", "+this.getMostRobustSon().getOptimalSequence(n-1);
	}
	
	public GoGameTree findBestMove(long time) {
		long init_time = System.currentTimeMillis();
		GoGameTree res = this.getMostRobustSon();
		
		return res;
	}
	
	public int getSize() {
		if (sons == null) return 1;
		
		int r = 1;
		for (GoGameTree s : sons) r += s.getSize();
		return r;
	}
}
